package com.algorithm.dp;

import static java.lang.Integer.max;

/**
 * 最大连续子序列和:
 * 给出数组arr = {1,-5,3,4,-2,2,3} 求其中连续的子数组最大值为多少?
 */
public class MaxSequenceSum {
    public static void main(String[] args) {
        int[] arr = {1, -5, 3, 4, -2, 2, 3};
        int res = maxSequenceSum(arr);
        System.out.println(res);
        res = maxSequenceSum1(arr);
        System.out.println(res);
    }

    /**
     * 要求最大子数组和,可以从头开始加,如果加的结果小于0了就重新开始加(前面和为负舍去值会更大)
     * 即 if(dp[i-1] >0) dp[i] = dp[i-1] + arr[i]
     * else dp[i] = arr[i]
     *
     * @param arr
     * @return
     */
    private static int maxSequenceSum(int[] arr) {
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        int max = arr[0];
        for (int i = 1; i < dp.length; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + arr[i];
            } else {
                dp[i] = arr[i];
            }
            max = max(max, dp[i]);
        }
        return max;
    }

    // 因为dp[i]只跟dp[i-1]有关,所以可以不使用数组
    private static int maxSequenceSum1(int[] arr) {
        int max = 0;
        int currentSum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (currentSum < 0){
                currentSum = arr[i];
            }else {
                currentSum +=arr[i];
            }
            if (currentSum > max){
                max = currentSum;
            }
            // 可以简化为以下写法(考虑使用max比较代替if/else)
            //currentSum = max(currentSum + arr[i], arr[i]);
            //max = max(max, currentSum);
        }
        return max;
    }
}
